package com.LeeCode;

import java.util.HashMap;

/**
 * 字符串的排列
 */

public class Code567 {
    public static void main(String[] args) {
        String s1 = "ccc";
        String s2 = "cbac";
        System.out.println(new Code567().checkInclusion(s1, s2));
    }

    public boolean checkInclusion(String s1, String s2) {
        HashMap<Character, Integer> target = new HashMap<>();
        HashMap<Character, Integer> current = new HashMap<>();

        for (char c : s1.toCharArray()) {
            target.put(c, target.getOrDefault(c, 0) + 1);
        }

        int diff = target.size(), window = s1.length();

        for (int i = 0; i < s2.length(); i++) {
            // 入
            char c = s2.charAt(i);
            if (target.containsKey(c)) {
                current.put(c, current.getOrDefault(c, 0) + 1);
                if (current.get(c).equals(target.get(c))) {
                    diff--;
                } else if (current.get(c) == target.get(c) + 1) {
                    diff++;
                }
            }

            if (i < window - 1) {
                continue;
            }
            // 更新
            if (diff == 0) {
                return true;
            }
            // 出
            int pos = i - window + 1;
            c = s2.charAt(pos);
            if (target.containsKey(c)) {
                if (current.get(c) == target.get(c) + 1) {
                    diff--;
                } else if (current.get(c).equals(target.get(c))) {
                    diff++;
                }
                current.put(c, current.get(c) - 1);
            }

        }
        return false;
    }
}
